489. Robot Room Cleaner
Hard

Given a robot cleaner in a room modeled as a grid.

Each cell in the grid can be empty or blocked.

The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.

When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

Design an algorithm to clean the entire room using only the 4 given APIs shown below.

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}

Example:

Input:
room = [
  [1,1,1,1,1,0,1,1],
  [1,1,1,1,1,0,1,1],
  [1,0,1,1,1,1,1,1],
  [0,0,0,1,0,0,0,0],
  [1,1,1,1,1,1,1,1]
],
row = 1,
col = 3

Explanation:
All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

Notes:

  1. The input is only given to initialize the room and the robot's position internally. You must solve this problem "blindfolded". In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot's position.
  2. The robot's initial position will always be in an accessible cell.
  3. The initial direction of the robot will be facing up.
  4. All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
  5. Assume all four edges of the grid are all surrounded by wall.
Accepted
83,439
Submissions
113,508
Seen this question in a real interview before?
Companies
Related Topics

Average Rating: 4.24 (114 votes)

Premium

Solution


Approach 1: Spiral Backtracking

Concepts to use

Let's use here two programming concepts.

The first one is called constrained programming.

That basically means to put restrictions after each robot move. Robot moves, and the cell is marked as visited. That propagates constraints and helps to reduce the number of combinations to consider.

bla

The second one called backtracking.

Let's imagine that after several moves the robot is surrounded by the visited cells. But several steps before there was a cell which proposed an alternative path to go. That path wasn't used and hence the room is not yet cleaned up. What to do? To backtrack. That means to come back to that cell, and to explore the alternative path.

bla

Intuition

This solution is based on the same idea as maze solving algorithm called right-hand rule. Go forward, cleaning and marking all the cells on the way as visited. At the obstacle turn right, again go forward, etc. Always turn right at the obstacles and then go forward. Consider already visited cells as virtual obstacles.

What do do if after the right turn there is an obstacle just in front ?

Turn right again.

How to explore the alternative paths from the cell ?

Go back to that cell and then turn right from your last explored direction.

When to stop ?

Stop when you explored all possible paths, i.e. all 4 directions (up, right, down, and left) for each visited cell.

Algorithm

Time to write down the algorithm for the backtrack function backtrack(cell = (0, 0), direction = 0).

  • Mark the cell as visited and clean it up.

  • Explore 4 directions : up, right, down, and left (the order is important since the idea is always to turn right) :

    • Check the next cell in the chosen direction :

      • If it's not visited yet and there is no obtacles :

        • Move forward.

        • Explore next cells backtrack(new_cell, new_direction).

        • Backtrack, i.e. go back to the previous cell.

      • Turn right because now there is an obstacle (or a virtual obstacle) just in front.

Implementation

bla

Complexity Analysis

  • Time complexity : O(NM)\mathcal{O}(N - M), where NN is a number of cells in the room and MM is a number of obstacles.

    • We visit each non-obstacle cell once and only once.
    • At each visit, we will check 4 directions around the cell. Therefore, the total number of operations would be 4(NM)4 \cdot (N-M).
  • Space complexity : O(NM)\mathcal{O}(N - M), where NN is a number of cells in the room and MM is a number of obstacles.

    • We employed a hashtable to keep track of whether a non-obstacle cell is visited or not.

Report Article Issue

Comments: 83
zzznotsomuch's avatar
Read More

I could not understand the problem without reading the solution. Please improve the problem description.

74
Show 4 replies
Reply
Share
Report
wangjian4814's avatar
Read More

It is a REAL hard problem. I think the point is ask as to figure out a small project, not a problem. We should consider the cordinate at first. I failed...so I copy the answer.

63
Show 2 replies
Reply
Share
Report
elegant_94's avatar
Read More

Randomly moving in 4 directions for 1million iterations works

18
Show 2 replies
Reply
Share
Report
kai99's avatar
Read More

i love this problem

43
Show 1 reply
Reply
Share
Report
calvinchankf's avatar
Read More

i am confused, why we need new_d = (d + i) % 4?

26
Show 13 replies
Reply
Share
Report
XeQtR_Dev's avatar
Read More

The solution starts the cleaning process from (0,0) if my understanding is correct. But isn't the robot supposed to be starting from a given position?
Can someone please help me out here.

10
Show 4 replies
Reply
Share
Report
hardfault's avatar
Read More

I think this question is not hard to implement. But hard to understand xD

14
Reply
Share
Report
jprakhar77's avatar
Read More

It's called concepts, not conceptions, IMO.

6
Show 3 replies
Reply
Share
Report
youjiahan's avatar
Read More

Each node is visited only once why the time complexity O(4^N-M)

8
Show 4 replies
Reply
Share
Report
abilityfun's avatar
Read More

@andvary, you are wrong on the time complexity. It is MN. The branching factor is 4 but we maintain a visited set. Hence, you will not visit the same square twice and complexity is limited to MN.

9
Show 3 replies
Reply
Share
Report
Success
Details
Runtime: 12 ms, faster than 80.54% of C++ online submissions for Robot Room Cleaner.
Memory Usage: 8.5 MB, less than 88.30% of C++ online submissions for Robot Room Cleaner.
Time Submitted
Status
Runtime
Memory
Language
06/16/2021 08:37Accepted12 ms8.5 MBcpp
06/16/2021 08:20Accepted12 ms8.6 MBcpp
05/29/2021 12:31Accepted12 ms8.7 MBcpp
05/27/2021 19:17Accepted8 ms8.6 MBcpp
05/27/2021 19:14Runtime ErrorN/AN/Acpp
/23
Contribute
|||
Saved
Trie
This list is empty.